

public class Sort {
    public int[] insertSort1(int[] arr){
        if (arr==null) return null;
        int i=1;
        int j=0;

        while(i<arr.length){
            int tmp= arr[i];
            j=i-1;

            while(j>=-1) {
                if (j == -1) {
                    arr[j + 1] = tmp;
                    i++;
                    break;
                }
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                    j--;
                }else{
                    arr[j+1]=tmp;
                    i++;
                    break;
                }
            }
        }
        return arr;
    }

    public int[] insertSort2(int[] arr){
        if (arr==null) return null;
        for (int i = 1; i <arr.length; i++) {
            int j = i-1;
            int tmp = arr[i];
            for (; j >=0; j--) {
                if(arr[j]>tmp){
                    arr[j+1]=arr[j];
                }else {
                    arr[j+1]=tmp;
                    break;
                }
            }

            arr[j+1]=tmp;
        }
        return arr;
    }

    public void shellSort(int[] array){
        int gap = array.length;
        while(gap!=1){
            gap/=2;
            shell(array,gap);
        }
    }

    private void shell(int[] array, int gap) {
        for (int i = gap; i <array.length ; i++) {
            int tmp = array[i];
            int j = i-gap;
            for(;j>=0;j-=gap){
                if (array[j]>tmp){
                    array[j+gap]=array[j];
                }else{
                    array[j+gap]=tmp;
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }

    //选择排序优化版
    public int[] selectSort1(int[] arr){
        int left=0;
        int right=arr.length-1;
        for (; left <right ; left++) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i <=right ; i++) {
                if (arr[i]<arr[minIndex]){
                    minIndex=i;
                }
                if (arr[i]>arr[maxIndex]){
                    maxIndex=i;
                }
            }
            swap(arr,left,minIndex);
            if (left==maxIndex) maxIndex=minIndex;
            swap(arr,maxIndex,right);
            right--;
        }
        return arr;
    }

    //选择排序初始版
    public int[] selectSort(int[] arr){
        for(int left=0;left<arr.length;left++){
            int minIndex = left;
            for (int j = left+1; j <arr.length; j++) {
                if (arr[j]<arr[minIndex]){
                    minIndex=j;
                }
            }
                swap(arr,minIndex,left);
        }
        return arr;
    }
    private void swap(int[] arr,int index1,int index2){
        int tmp1=arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=tmp1;
    }


}
